package com.kdtree;

import java.util.Arrays;

public class MinPriQueue {
	// Minimizing Priority Queue

	// array containing priority queue
	MinPriNode[] pqArray;

	// number of elements allocated
	int nAllocated;

	// number of elements in the priority queue
	int n;

	private static final String LINE = "no line";
	private static final String FILE = "MinPriQueue";
	private static final int MINPQ_INIT_NALLOCD = 512;

	private static int parent(int i) {
		return (i - 1) / 2;
	}

	/* returns the array index of element i's right child */
	private static int right(int i) {
		return 2 * i + 2;
	}

	/* returns the array index of element i's left child */
	private static int left(int i) {
		return 2 * i + 1;
	}

	/********************** Functions prototyped in minpq.h **********************/
	/*
	Creates a new minimizing priority queue.
	*/
	public MinPriQueue() {
		this.pqArray = new MinPriNode[MINPQ_INIT_NALLOCD];
		this.nAllocated = MINPQ_INIT_NALLOCD;
		this.n = 0;
	}

	/**
	Inserts an element into a minimizing priority queue.

	@param data the data to be inserted
	@param key the key to be associated with \a data

	@return Returns 0 on success or 1 on failure.
	*/
	int insert(Object data, int key) {
		int n = this.n;

		/* double array allocation if necessary */
		if(this.nAllocated == n) {
			this.pqArray = Arrays.copyOf(this.pqArray, this.pqArray.length * 2);
			this.nAllocated = this.pqArray.length;

			if(this.nAllocated == 0) {
				System.err.format("Warning: unable to allocate memory, %s, line %d\n", FILE, LINE);
				return 1;
			}
		}

		this.pqArray[n] = new MinPriNode();
		this.pqArray[n].data = data;
		this.pqArray[n].key = Integer.MAX_VALUE;
		decreasePQNodeKey(this.pqArray, this.n, key);
		this.n++;

		return 0;
	}

	/**
	Returns the element of a minimizing priority queue with the smallest key
	without removing it from the queue.

	@return Returns the element of \a min_pq with the smallest key or null
	if \a min_pq is empty
	*/
	Object getMin() {
		if(this.n < 1) {
			System.err.format("Warning: PQ empty, %s line %d\n", FILE, LINE);
			return null;
		}
		return this.pqArray[0].data;
	}
	/**
	 * Removes and returns the element of a minimizing
	 * priority queue with the smallest key.
	 *
	 * @return the element of \a min_pq with the smallest key
	 * of null if \a min_pq is empty
	 */
	
	/**
	 *
	Removes and returns the element of a minimizing priority queue with the
	smallest key.

	@return Returns the element of \a min_pq with the smallest key of null
	if \a min_pq is empty
	*/
	Object extractMin() {
		Object data;

		if(this.n < 1) {
			System.err.format("Warning: PQ empty, %s line %d\n", FILE, LINE);
			return null;
		}
		data = this.pqArray[0].data;
		this.n--;
		this.pqArray[0] = this.pqArray[this.n];
		restoreOrder(this.pqArray, 0, this.n);

		return data;
	}


	/*
	De-allocates the memory held by a minimizing priorioty queue

	@param min_pq pointer to a minimizing priority queue
	*/
//	void minpq_release( MinPriQueue* min_pq )
//	{
//		if( min_pq == null )
//		{
//			System.err.format("Warning: null pointer error, %s line %d\n", FILE,
//					LINE );
//			return;
//		}
//		if( *min_pq  &&  (*min_pq).pqArray )
//		{
//			free( (*min_pq).pqArray );
//			free( *min_pq );
//			*min_pq = null;
//		}
//	}


	/************************ Functions prototyped here **************************/

	/**
	Decrease a minimizing pq element's key, rearranging the pq if necessary

	@param pqArray minimizing priority queue array
	@param i index of the element whose key is to be decreased
	@param key new value of element <EM>i</EM>'s key; if greater than current
		key, no action is taken
	*/
	void decreasePQNodeKey(MinPriNode[] pqArray, int i, int key) {
		MinPriNode tmp;

		if(key > pqArray[i].key) {
			return;
		}

		pqArray[i].key = key;
		while(i > 0  &&  pqArray[i].key < pqArray[parent(i)].key) {
			tmp = pqArray[parent(i)];
			pqArray[parent(i)] = pqArray[i];
			pqArray[i] = tmp;
			i = parent(i);
		}
	}

	/**
	Recursively restores correct priority queue order to a minimizing pq array

	@param pqArray a minimizing priority queue array
	@param i index at which to start reordering
	@param n number of elements in \a pqArray
	*/
	void restoreOrder(MinPriNode[] pqArray, int i, int n) {
		MinPriNode tmp;
		int l, r, min = i;

		l = left(i);
		r = right(i);
		if(l < n) {
			if(pqArray[l].key < pqArray[i].key) {
				min = l;
			}
		}
		if(r < n) {
			if(pqArray[r].key < pqArray[min].key) {
				min = r;
			}
		}

		if(min != i) {
			tmp = pqArray[min];
			pqArray[min] = pqArray[i];
			pqArray[i] = tmp;
			restoreOrder(pqArray, min, n);
		}
	}
}
